package OptimalAlgorithm.SlidingWindow;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

//给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
//eg:
//输入: s = "cbaebabacd", p = "abc"
//输出: [0,6]
//解释:
//起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
//起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
public class FindAnagrams {
/*    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        char[] str = s.toCharArray();
        char[] p1 = p.toCharArray();
        int len = p1.length;
        if(str.length < len){
            return list;
        }
        HashMap<Character,Integer> hashs = new HashMap<>();
        HashMap<Character,Integer> hashp = new HashMap<>();
        for (char c : p1) {
            hashp.put(c, hashp.getOrDefault(c, 0) + 1);
        }
        for(int left = 0,right = 0;right < str.length;right++){
            hashs.put(str[right],hashs.getOrDefault(str[right],0) + 1);//进窗口
            if(right - left + 1 > len){//判断
                if(hashs.get(str[left]) == 1){
                    hashs.remove(str[left]);
                }else {
                    hashs.put(str[left],hashs.get(str[left]) - 1);
                }
                left++;
            }
            if(hashs.equals(hashp)){
                //hash表相同，更新结果
                list.add(left);
            }
        }
        return list;
    }*/
/*    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        char[] str = s.toCharArray();
        char[] p1 = p.toCharArray();
        int len = p1.length;
        if(str.length < len){
            return list;
        }
        int[] hashs = new int[26];
        int[] hashp = new int[26];
        for (int i = 0; i < len; i++) {
            hashp[p1[i] - 97]++;
        }
        for(int left = 0,right = 0;right < str.length;right++){
            hashs[str[right] - 97]++;
            if(right - left + 1 > len){
                hashs[str[left] - 97]--;
                left++;
            }
            if(check(hashs,hashp)){
                list.add(left);
            }
        }
        return list;
    }
    public boolean check(int[] hashs,int[] hashp){
        for(int i = 0; i < 26;i++){
            if(hashp[i] != hashs[i]){
                return false;
            }
        }
        return true;
    }*/
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        char[] str = s.toCharArray();
        char[] p1 = p.toCharArray();
        int len = p1.length;
        if(str.length < len){
            return list;
        }
        int[] hashs = new int[26];
        int[] hashp = new int[26];
        int count = 0;//利用count变量来表示窗口中“有效个数”，当count == len说明是异位词
        for (char c : p1) {
            hashp[c - 97]++;
        }
        for(int left = 0,right = 0;right < str.length;right++){
            hashs[str[right] - 97]++;//进窗口
            //进窗口后的时候更新一下count
            if(hashs[str[right] - 97] <= hashp[str[right] - 97]){
                count++;
            }
            if(right - left + 1 > len){//判断
                //出窗口前的时候更新一下count的值
                if(hashs[str[left] - 97] <= hashp[str[left] - 97]){
                    count--;
                }
                hashs[str[left] - 97]--;//出窗口
                left++;
            }
            if(count == len){
                list.add(left);
            }
        }
        return list;
    }
}
